package algorithm;

import java.util.Arrays;

/**
 * 922. 按奇偶排序数组 II
 */
public class T00922 {
    public static void main(String[] args) {
        int[] arr = new int[]{1,1,1,1,1,2,2,2,2,2};
        int[] arr1 = new Solution().
                sortArrayByParityII(arr);
        checkEven(arr);
        System.out.println(Arrays.toString(arr1));
    }

    static void checkEven(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            if(((i | arr[i]) & 0b1) == 0 || ((i ^ arr[i]) & 0b1) == 0)
                continue;
            throw new RuntimeException(String.valueOf(i));
        }
    }

static class Solution {
    public int[] sortArrayByParityII(int[] A) {
        if(A == null || A.length <= 1)
            return A;
        int limit = A.length;
        int i = 0, j = 1; // 奇数指针和偶数指针
        while(i < limit && j < limit) {
            while(i < limit && (A[i] & 0b1) == 0)
                i += 2;
            if(i >= limit)
                break;
            while(j < limit && (A[j] & 0b1) == 1)
                j += 2;
            if(j >= limit)
                break;

            // 交换
            int t = A[i];
            A[i] = A[j];
            A[j] = t;
            i += 2;
            j += 2;
        }
        return A;
    }
}
}